/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2025-01-15
 * @Description: 猫狗队列
 * TODO: 测试未通过
 *******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Pet {
    char type[5];
    int id;
    int count;
} Pet;

typedef struct Node {
    Pet *pet;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front, *rear;
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = NULL;
}

bool isQueueEmpty(Queue *q) {
    return q->front == NULL;
}

void enqueue(Queue *q, Pet *pet) {
    Node *node = malloc(sizeof(Node));
    node->next = NULL;
    node->pet = pet;
    if (q->rear == NULL)
        q->front = q->rear = node;
    else {
        q->rear->next = node;
        q->rear = node;
    }
}

Pet *dequeue(Queue *q) {
    if (isQueueEmpty(q))
        return NULL;
    Node *temp = q->front;
    q->front = temp->next;
    if (q->front == NULL)
        q->rear = NULL;
    Pet *pet = temp->pet;
    return pet;
}

typedef struct {
    Queue dog_queue;
    Queue cat_queue;
} CatDogQueue;

void initCatDogQueue(CatDogQueue *ptr) {
    initQueue(&ptr->cat_queue);
    initQueue(&ptr->dog_queue);
}

void addPet(CatDogQueue *q, Pet *pet) {
    if (strcmp(pet->type, "dog") == 0)
        enqueue(&q->dog_queue, pet);
    else
        enqueue(&q->cat_queue, pet);
}

Pet *pollDog(CatDogQueue *q) {
    return dequeue(&q->dog_queue);
}

Pet *pollCat(CatDogQueue *q) {
    return dequeue(&q->cat_queue);
}

Pet *pollAll(CatDogQueue *q) {
    if (!isQueueEmpty(&q->cat_queue) && !isQueueEmpty(&q->dog_queue)) {
        Pet *dog = q->dog_queue.front->pet;
        Pet *cat = q->cat_queue.front->pet;
        if (dog->count < cat->count)
            return pollDog(q);
        else
            return pollCat(q);
    } else if (!isQueueEmpty(&q->cat_queue))
        return pollCat(q);
    else
        return pollDog(q);
}

bool isEmpty(CatDogQueue *q) {
    return isQueueEmpty(&q->cat_queue) && isQueueEmpty(&q->dog_queue);
}

bool isCatEmpty(CatDogQueue *q) {
    return isQueueEmpty(&q->cat_queue);
}

bool isDogEmpty(CatDogQueue *q) {
    return isQueueEmpty(&q->dog_queue);
}

int main() {
    int n;
    scanf("%d", &n);
    getchar();

    CatDogQueue queue;
    initCatDogQueue(&queue);

    char output[1000][50];
    int index = 0;
    int count = 0;
    // 把line声明在循环外，在sscanf执行时对line修改，防止对output修改
    char line[100];
    char opt[10];
    char type[5];
    int id;

    for (int i = 0; i < n; ++i) {
        fgets(line, sizeof(line), stdin);
        line[strcspn(line, "\n")] = 0;

        sscanf(line, "%s", opt);

        if (strcmp(opt, "add") == 0) {
            sscanf(line, "%s %s %d", opt, type, &id);
            Pet *pet = malloc(sizeof(Pet));
            strcpy(pet->type, type);
            pet->id = id;
            pet->count = count++;
            addPet(&queue, pet);
        } else if (strcmp(opt, "pollAll") == 0) {
            while (!isEmpty(&queue)) {
                Pet *pet = pollAll(&queue);
                sprintf(output[index++], "%s %d", pet->type, pet->id);
                if (pet != NULL)
                    free(pet);
            }
        } else if (strcmp(opt, "pollDog") == 0) {
            while (!isDogEmpty(&queue)) {
                Pet *pet = pollDog(&queue);
                sprintf(output[index++], "%s %d", pet->type, pet->id);
                if (pet != NULL)
                    free(pet);
            }
        } else if (strcmp(opt, "pollCat") == 0) {
            while (!isCatEmpty(&queue)) {
                Pet *pet = pollCat(&queue);
                sprintf(output[index++], "%s %d", pet->type, pet->id);
                if (pet != NULL)
                    free(pet);
            }
        } else if (strcmp(opt, "isEmpty") == 0) {
            sprintf(output[index++], "%s", isEmpty(&queue) ? "yes" : "no");
        } else if (strcmp(opt, "isDogEmpty") == 0) {
            sprintf(output[index++], "%s", isDogEmpty(&queue) ? "yes" : "no");
        } else if (strcmp(opt, "isCatEmpty") == 0) {
            sprintf(output[index++], "%s", isCatEmpty(&queue) ? "yes" : "no");
        }
    }

    for (int i = 0; i < index; ++i) {
        if (i > 0)
            printf("\n");
        printf("%s", output[i]);
    }

    return 0;
}
